import java.util.Arrays;

public class Sort {
   public static void insertSort(int[]array){
       for (int i = 1; i < array.length; i++) {
           int tmp=array[i];
           int j = i-1;
           for (; j >=0; j--) {
               if(array[j]>tmp){
                   array[j+1]=array[j];
               }else{
                   break;
               }
           }
           array[j+1]=tmp;
       }
   }

   public static void selectSort(int[]array){
       for (int i = 0; i < array.length; i++) {
           for (int j = i+1; j <array.length ; j++) {
               if(array[j]<array[i]){
                   int tmp=array[i];
                   array[i]=array[j];
                   array[j]=tmp;
               }
           }
       }
   }

   public static void HeapSort(int []array){
       createHeap(array);
       int end=array.length-1;
       while(end>0){
           int tmp=array[0];
           array[0]=array[end];
           array[end]=tmp;
           shiftDown(array,0,end);
           end--;
       }
   }

   public static void createHeap(int[]array){
       for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
           shiftDown(array,parent,array.length);
       }
   }
   public static void shiftDown(int[]array,int parent,int len){
       int child=2*parent+1;
       while(child<len){
           if(child+1<len&&array[child+1]>array[child]){
               child++;
           }
           if(array[parent]<array[child]){
               int tmp=array[parent];
               array[parent]=array[child];
               array[child]=tmp;
               parent=child;
               child=2*parent+1;
           }else{
               break;
           }
       }
   }

   public static void bubbleSort(int[]array){
       for (int i = 0; i < array.length; i++) {
           for (int j = 0; j < array.length-1-i; j++) {
               if(array[j]>array[j+1]){
                   int tmp=array[j];
                   array[j]=array[j+1];
                   array[j+1]=tmp;
               }
           }
       }
   }

   public static void quickSort(int[]array){
       quick(array,0,array.length-1);
   }
   public static void quick(int[]array,int left,int right){
       if(left>=right){
           return;
       }
       int midValIndex=findMidValIndex(array,left,right);
       int tmp=array[midValIndex];
       array[midValIndex]=array[left];
       array[left]=tmp;
       int pivot=partition(array,left,right);
       quick(array,left,pivot-1);
       quick(array,pivot+1,right);
   }
   public static int partition(int[]array,int start,int end){
       int tmp=array[start];
       while(start<end){
           while(start<end&&array[end]>=tmp){
               end--;
           }
           array[start]=array[end];
           while(start<end&&array[start]<=tmp){
               start++;
           }
           array[end]=array[start];
       }
       array[start]=tmp;
       return start;
   }

   public static int findMidValIndex(int[]array,int start,int end){
       int mid=start+((end-start)>>>1);
       if (array[start] < array[end]) {
           if(array[mid]<array[start]){
               return start;
           }else if(array[mid]>array[end]){
               return end;
           }else{
               return mid;
           }
       }else{
           if(array[mid]>array[start]){
               return start;
           }else if(array[mid]<array[end]){
               return end;
           }else{
               return mid;
           }
       }

   }

    public static void mergeSort(int[]array){
       mergeInternal(array,0,array.length-1);
    }
    public static void mergeInternal(int[]array,int left,int right){
       if(left>=right){
           return;
       }
       int mid=left+((right-left)>>>1);
       mergeInternal(array,left,mid);
       mergeInternal(array,mid+1,right);
       merge(array,left,mid,right);
    }
    public static void merge(int[]array,int start,int mid,int end){
       int []tmp=new int[end-start+1];
       int k=0;
       int s1=start;
       int e1=mid;
       int s2=mid+1;
       int e2=end;
       while(s1<=e1&&s2<=e2){
           if(array[s1]<array[s2]){
               tmp[k++]=array[s1++];
           }else{
               tmp[k++]=array[s2++];
           }
       }
       while(s1<=e1){
           tmp[k++]=array[s1++];
       }
       while(s2<=e2){
           tmp[k++]=array[s2++];
       }
        for (int i = 0; i < k; i++) {
            array[i+start]=tmp[i];
        }
    }

    public static void main(String[] args) {
        int []array={33,22,11,55,23,34};
        //insertSort(array);
        //selectSort(array);
        //HeapSort(array);
        //bubbleSort(array);
        //quickSort(array);
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
